package com.zhj.algorithm.search.str;

public class BMSearch implements StrSearch {

    @Override
    public int search(String A, String B) {
        if (A == null || A.length() == 0 || B == null || B.length() == 0 || A.length() < B.length()) {
            return -1;
        }
        int start = 0;
        while (start <= A.length() - B.length()) {
            int i;
            for (i= B.length() - 1; i >= 0; i--) {
                if (A.charAt(start + i) != B.charAt(i)) {
                    break;
                }
            }
            if (i < 0) {
                return start + 1;
            }
            int charIndex = findCharacter(B, A.charAt(start+i), i);
            int bcOffset = charIndex >= 0 ? i-charIndex : i+1;
            start += bcOffset;
        }
        return -1;
    }

    private int findCharacter(String B, char badCharacter, int index) {
        for (int i = index-1; i >= 0; i--) {
            if (B.charAt(i) == badCharacter) {
                return i;
            }
        }
        return -1;
    }

}
